/* This version of htab is simplified for non-negative integer keys, the memory footprint should be predictable, that is, no allocation is supported */
#pragma once
#include <sys/cdefs.h>
#include "i32_divisor.hpp"
#include <cassert>
// #include <cstdio>
template<typename KeyType, int Capacity>
struct mini_hset{
  static constexpr i32_divisor cap = i32_divisor(Capacity);
  static constexpr KeyType empty = -1;
  KeyType keys[Capacity];
  mini_hset(){
    for (int i = 0; i < Capacity; i ++) keys[i] = empty;
  }
  int get_slot(const KeyType &key) const {
    int slot = key % Capacity;
    while ((keys[slot] != key) & (keys[slot] != empty)) {
      slot ++;
      if (slot >= Capacity) slot = 0;
    }
    return slot;
  }

  bool contains(const KeyType &key) const {
    int slot = this->get_slot(key);
    return keys[slot] == key;
  }
  void insert(const KeyType &key) {
    int slot = this->get_slot(key);
    keys[slot] = key;
  }
  int size(){
    int ret = 0;
    for (int i = 0; i < Capacity; i ++)
      if (keys[i] != empty) ret ++;
    return ret;
  }
};
template<typename KeyType, typename ValType, int Capacity>
struct mini_htab : public mini_hset<KeyType, Capacity> {
  ValType vals[Capacity];
  mini_htab() : mini_hset<KeyType, Capacity>(){
  }
  
  const ValType &operator[](const KeyType &key) const {
    int slot = this->get_slot(key);
    if (slot != -1) {
      return vals[slot];
    } else {
      return *(ValType*)nullptr;
    }
  }
  ValType &operator[](const KeyType &key) {
    int slot = this->get_slot(key);
    this->keys[slot] = key;
    return vals[slot];
  }
};
// int main(){
//   mini_htab<long, int, 32> tab;
//   tab[0] = 0;
//   const auto &tab_ro = tab;
//   tab_ro[1];
//   // tab[0] = 10;
//   // tab[0x3ff] = 20;
//   // printf("%d %d\n", tab[0], tab.ro[0x3ff]);
// }
